// 862. 和至少为 K 的最短子数组
// https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
// 给你一个整数数组 nums 和一个整数 k ，
// 找出 nums 中和至少为 k 的 最短非空子数组，
// 并返回该子数组的长度。
// 如果不存在这样的子数组 ，返回 -1 。
// 子数组 是数组中 连续 的一部分。
// 解
// 1.使用前缀和的差来计算子数组的和；
// 2.使用一种数据结构，将当前前缀和i与最前面的前缀和j作差，
// 如果满足>=k的条件，那么j在之后就可以不用看了。
// 【因为即使后面也有满足条件的，长度也会更长，所以需要将j从前面弹出】；
// 3.当前的i也要放入数据结构，那么如果数据结构中有前缀和j比前缀和i大，
// j也可以不用看了。【因为即使后面有满足条件的，与i作差肯定也满足条件，
// 并且长度更短，所以需要将大于等于i的从后面弹出】。
// 前面后面都要弹出，压入的元素满足单调性，所以使用单调队列。
// ---
// 优化1.
//      s[i]
// s[j]
// s[i]-s[j]>=k
// 优化2.
// s[j]
//     s[i]
// s[j]>s[i]

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> preSums(n+1);
        deque<int> qu;
        for(int i = 0; i < n; i++) {
            preSums[i+1] = preSums[i] + nums[i];
        }
        int res = n + 1;
        for(int i=0; i<=n; i++) {
            while (!qu.empty() && preSums[i] - preSums[qu.front()] >= k) {
                res = min(res, i-qu.front());
                 qu.pop_front();
            }
            while (!qu.empty() && preSums[qu.back()] >= preSums[i]) {
                qu.pop_back();
            }
            qu.push_back(i);
        }
        return res == n+1 ? -1:res;
    }
};

int main() {
    printf("size:%d %d\n", sizeof(long), sizeof (int));
  Solution sol;
  vector<int> nums = {1,5,4,9,4,-2,-4,6};
  sol.shortestSubarray(nums,15);
  for (auto nn : nums) PF("%d,", nn);
  PF("\n");
  return 0;
}

